package q733_floodFill;

public class Solution_1 {

    int[] dx = {1, 0, 0, -1};
    int[] dy = {0, 1, -1, 0};

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {

        int currColor = image[sr][sc];
        // 如果要改的color和newColor一样 就不用dfs了
        if (currColor != newColor) {
            dfs(sr, sc, image, currColor, newColor);
        }
        return image;
    }

    /*
    此方法一般和一般的迭代模版有所不同
    对于一个在二维数组里进行dfs
    一般要定义四个方向来进行帮助搜索 也就是建立dx dy 或者直接建立到一个二维数组dxy也可({0,1} {1,0} {0,-1} {-1,0}})
     */
    private void dfs(int r, int c, int[][] image, int color, int newColor) {
        // 相较于原来的dfs模版 ——> if 终止条件 for (操作逻辑 dfs 取消操作逻辑)
        // 这种在二维数组中的搜索问题的操作的有所不同
        // 一般将循环定义为四个方向的搜索
        if (image[r][c] != color) {
            return;
        }
        // 此题要先改颜色
        image[r][c] = newColor;
        // for循环代表四个方向
        for (int i = 0; i < 4; i++) {
            int next_r = r + dx[i], next_c = c + dy[i];
            if (next_r >= 0 && next_r < image.length && next_c >= 0 && next_c < image[0].length) {
                dfs(next_r, next_c, image, color, newColor);
            }
        }

    }


}
